/*	Interactive Gravitational Simulator
	Project: IGS Core
	File: TreeBase.h
	Author: Mike Bantegui <mbante2@gmail.com>, Hofstra University 
	Copyright (C) 2012 - 2013 Mike Bantegui

	This file is part of the IGS software package for simulating
	the N-Body problem in real-time. This was developed as part
	of a departmental honors thesis project at Hofstra University
	in the Spring 2012 semester.

	IGS is free software; you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation; either version 2 of the License, or
	(at your option) any later version.

	IGS is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program; if not, write to the Free Software
	Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
*/

#ifndef IGS_TREEBASE_H
#define IGS_TREEBASE_H

#include "Configuration.h"
#include <vector>

namespace IGS
{

struct Body;
struct Node;
struct Vector;
class NBodySystem;

// Represents an abstract tree data structure for spatially sudviding space
// to accelerate the force evaluation. The current tree implementation is
// parallelized on evaluation by using a direct force evaluator. An optional
// pool memory allocator is available to allow one-time memory allocation
// and deallocation to be performed. In this mode, the time taken to deallocate
// the tree is greatly reduced
class Tree
{
protected:
	// The root of the Tree
	Node *Root;
	// The opening parameter which controls the accuracy of the simulation
	const double ThetaSq;
	// The number of branches stored in a interior node
	const unsigned BranchSize;
	// The number of bodies stored at a leaf node
	const unsigned LeafSize;
	// The time spent creating the tree
	double _CreateTime;
	// The time spent walking the tree
	double _EvaluateTime;
	// The time spent deleting the tree
	double _DeleteTime;

public:
	Tree(const double theta, const unsigned branchSize);
	Tree(const double theta, const unsigned branchSize, const unsigned leafSize);
	virtual ~Tree();

	void Evaluate(NBodySystem &system);

	double CreateTime() const;
	double EvaluateTime() const;
	double DeleteTime() const;

	virtual std::string Name() const = 0;

#ifdef PoolAllocator
	void SetPoolSize(int N);
#endif

protected:
#ifdef PoolAllocator
	virtual unsigned CalculatePoolSize(const int N) const = 0;
#endif
	virtual Node *Branch(std::vector<Body *> bodies, const Vector &min, const Vector &max, const unsigned depth) = 0;

	Node *AllocateNode(std::vector<Body *> &bodies);
	Node *AllocateNode(std::vector<Node *> &branches);

private:
#ifdef PoolAllocator
	// The actual size of the memory pool
	unsigned PoolSize;
	// The index into the memory pool
	unsigned PoolPointer;
	// The pool of nodes to allocate from
	Node *Pool;
#endif

	void CreateTree(NBodySystem &system);
	void DeleteTree();
};

}

#endif